//
// Created by REEJI2219 on 2024-09-29.
//
#include <iostream>
using namespace std;
typedef int ElemType;
class Node {
public:
    ElemType data;
    Node *next;
    ~Node() {
        next = nullptr;
    }
};
class NodeList {
public:
    Node *head;
    NodeList() {
        head = new Node();
        head->next=nullptr;
    }
    ~NodeList() {
        Node *deleteNode = head;
        //删除非头节点
        while (head->next) {
            deleteNode = head;
            head=head->next;
            delete deleteNode;
        }
        delete head;
    }

    /**
     * 尾部插入数据
     * 插入 顺序为 1 2 3 4
     * 列表中顺序为 1 2 3 4
     * 比如遍历到尾部
     * @param element 数据
     */
    void insert(ElemType element) {
        Node *last = head;
        while (last->next!=nullptr) {
            last = last->next;
        }
        Node *node = new Node();
        node->data = element;
        last->next= node;
    }

    /**
     * 头插法，直接在头结点插入元素
     * @param element 数据元素
     */
    void headInsert(ElemType element) {
        Node *node = new Node();
        node->data = element;
        node->next = head->next;
        head->next = node;
    }

    /**
     * 使用头插法实现链表翻转
     */
    void revoal() {
        Node *newHead = new Node();
        Node *current = head;
        //移动到第一个节点，
        current =current->next;
        //第一个节点有后续，则继续
        while (current->next!=nullptr) {
            //记录当前节点
            Node *node = current;
            //头节点后移
            current =current->next;
            //当前节点后续为空
            node->next = nullptr;
            //头插法实现翻转
            node->next = newHead->next;
            newHead->next = node;
        }
        //最后一个节点设置为第一个节点
        current->next = newHead->next;
        newHead->next = current;
        head = newHead;
    }

    /**
     * 获取第i个元素的数据
     * @param i 第几个位置
     * @param result 结果
     * @return 能否获取到
     */
    bool getElement(int i,ElemType &result) {
        if(i<1) {
            return false;
        }
        int j=1;
        Node *current = head->next;
        while (current->next!=nullptr && j<i) {
            current=current->next;
            j++;
        }
        if(j<i) {
            return  false;
        }
        result = current->data;
        return true;
    }

    /**
     * 删除指定元素
     * @param i 第几个原始
     * @param result 结果
     * @return 是否删除成功
     */
    bool deleteElement(int i,ElemType &result) {
        if(i<1) {
            return false;
        }
        int j=1;
        Node *current = head->next;
        //获取当前位置的上一个节点
        while (current->next!=nullptr && j<i-1) {
            current=current->next;
            j++;
        }
        if(j!=i-1) {
            return  false;
        }
        Node *deleteNode = current->next;
        if(deleteNode!=nullptr) {
            result = deleteNode->data;
            current->next = current->next->next;
            delete deleteNode;
        }
        return true;
    }
    void print() {
        Node *current=head;
        while (current->next!=nullptr) {
            current = current->next;
            printf("%d ",current->data);
        }
        printf("\n");
    }

};

int main(int argc, char *argv[]) {
    NodeList *list = new NodeList();
    list->insert(1);
    list->insert(2);
    list->insert(3);
    list->insert(4);
    list->print();
    // list->revoal();
    // list->print();
    int result;
    list->getElement(2,result);
    printf("%d \n",result);
    list->deleteElement(3,result);
    printf("%d \n",result);
    list->print();

}
